/*!
 * \file heur.c
 *
 * \date Sep 24, 2013
 * \author Ricardo C. Corrêa (correa@lia.ufc.br)
 *
 * \brief Heuristics for coloring, maximum stable set and maximum clique.
 */

#include <stdlib.h>
#include <bitmap.h>
#include <graph.h>
#include <heur.h>

static NODETYPE * RR; //!< Auxiliary bitmap used in various heuristics.
static Graph * heurg; //!< Input graph of the heuristics.
static size_t memsz = 0; //!< Memory space used by the heuristics.

// mcsColoring
static int * cover = NULL; //!< Vertices classified by colors
static int * idx; //!< First vertex of each color in \c cover

// fracColoring
static NODETYPE * E = NULL; //!< Auxiliary bitmap used in \c fracColoring.
static NODETYPE * EE; //!< Auxiliary bitmap used in \c fracColoring.
static NODETYPE * S; //!< Auxiliary bitmap used in \c fracColoring.

void initHeur(Graph * g) {
	heurg = g;
	int nnodes = NODEIDX(g->n-1) + 1;
	RR = (NODETYPE *) calloc(nnodes, WSIZE);
	memsz += (nnodes << LOGW);
}

void closeHeur() {
	free(RR);
	RR = NULL;
	heurg = NULL;

	if (cover != NULL) {
		free(cover);
		cover = NULL;
	}

	if (E != NULL) {
		free(E);
		E = NULL;
		EE = NULL;
	}
}

size_t getMemSize() {
	return memsz;
}

/*!
 * \fn int greedyColoring(NODETYPE * R, NODETYPE * W, int lim, int * minRNode, int * maxRNode, int * minWNode, int * maxWNode)
 * \brief Greedy heuristic for vertex coloring
 *
 * The vertices in the specified bitmap are colored, removed from this bitmap, and stored in another specified bitmap.
 * A maximum number of colors is specified. Vertices that cannot be colored with this number of colors remains in the input bitmap.
 *
 * The smallest and greatest indices of non-zero nodes of the specified bitmaps are updated.
 *
 * If \c R[\c *minRNode\c ] \c == \c 0, then an error may occur.
 *
 * \param R Input bitmap of vertices to color.
 * \param W Output bitmap to store vertices as soon as they are colored.
 * \param lim Maximum number of colors that can be used.
 * \param minRNode Smallest index of a non-zero node of the input bitmap.
 * \param maxRNode Greates index of a non-zero node of the input bitmap.
 * \param minWNode Smallest index of a non-zero node of the output bitmap.
 * \param maxWNode Greates index of a non-zero node of the output bitmap.
 *
 * \return The number of colors used.
 */
double greedyColoring(NODETYPE * R, NODETYPE * W, const double * w, double lim,
		int * minRNode, int * maxRNode, int * minWNode, int * maxWNode) {
	double size = 0.0;
	int vidx = 0;
	int nodeidx;
	int lastnodeidx = 0;
	NODETYPE * nodeR;
	NODETYPE * nodeRR;
	NODETYPE * nodeW;
	int minRRNode, minRRidx;

	int v;
	// find vertex to a new color: weight of this vertex is the weight of a new color. It must be bounded by lim
	nodeidx = *minRNode;
	copyAll(RR, R, nodeidx, *maxRNode + 1);
	nodeRR = (RR + nodeidx);
	do {
		while (nodeidx <= *maxRNode && (vidx = NODELEAST(*nodeRR)) < 0) {
			nodeidx = minNode(RR, nodeidx + 1, *maxRNode + 1);
			nodeRR = (RR + nodeidx);
		}
		if (vidx >= 0) {
			v = NELEM(nodeidx) + vidx;
			if (size + w[v] > lim) {
				v = -1;
				*nodeRR = DELFROMNODE(*nodeRR, vidx);
			} else {
				minRRNode = nodeidx;
				minRRidx = vidx;
			}
		} else
			v = -1;
	} while (vidx >= 0 && v < 0);

	while (v >= 0) {
		// create new color with weight of v
		size += w[v];
		if (nodeidx < *minWNode)
			*minWNode = nodeidx;
		while (vidx >= 0) {
			removeAll(RR, NEIG(heurg, NELEM(nodeidx)+vidx), nodeidx,
					*maxRNode + 1);
			*nodeRR = DELFROMNODE(*nodeRR, vidx);
			nodeR = (R + nodeidx);
			*nodeR = DELFROMNODE(*nodeR, vidx);
			nodeW = (W + nodeidx);
			*nodeW = ADDTONODE(*nodeW, vidx);
			lastnodeidx = nodeidx;
			nodeidx = minNode(RR, nodeidx, *maxRNode);
			nodeRR = (RR + nodeidx);
			vidx = NODELEAST(*nodeRR);
		}
		if (lastnodeidx > *maxWNode)
			*maxWNode = lastnodeidx;
		*minRNode = minNode(R, *minRNode, *maxRNode);
		*maxRNode = maxNode(R, *maxRNode, *minRNode);

		// find vertex to a new color: weight of this vertex is the weight of a new color. It must be bounded by lim
		nodeidx = minRRNode;
		copyAll(RR, R, nodeidx, *maxRNode + 1);
		nodeRR = (RR + nodeidx);
		*nodeRR = *nodeRR & (-1LL << (minRRidx + 1));
		do {
			while (nodeidx <= *maxRNode && (vidx = NODELEAST(*nodeRR)) < 0) {
				nodeidx = minNode(RR, nodeidx + 1, *maxRNode + 1);
				nodeRR = (RR + nodeidx);
			}
			if (vidx >= 0) {
				v = NELEM(nodeidx) + vidx;
				if (size + w[v] > lim) {
					v = -1;
					*nodeRR = DELFROMNODE(*nodeRR, vidx);
				} else {
					minRRNode = nodeidx;
					minRRidx = vidx;
				}
			} else
				v = -1;
		} while (vidx >= 0 && v < 0);
	}

	return size;
}

/*!
 * \fn int maxClique(NODETYPE * R, int minRNode, int maxRNode)
 * \brief Greedy heuristic for maximum clique.
 *
 * The vertices in the specified bitmap are greedily searched for a maximum clique.
 *
 * If \c R[\c *minRNode\c ] \c == \c 0, then an error may occur.
 *
 * \param R Input bitmap of vertices to color.
 * \param minRNode Smallest index of a non-zero node of the input bitmap.
 * \param maxRNode Greates index of a non-zero node of the input bitmap.
 *
 * \return The size of the clique found.
 */
double maxClique(NODETYPE * R, const double * w, int minRNode, int maxRNode) {
	int nodeidx = minRNode;
	copyAll(RR, R, nodeidx, maxRNode + 1);

	NODETYPE * nodeRR = (RR + nodeidx);
	int vidx = NODELEAST(*nodeRR);
	double size = 0.0;
	while (vidx >= 0) {
		int v = NELEM(nodeidx) + vidx;
		size += w[v];
		retainAll(RR, NEIG(heurg, v), nodeidx, maxRNode + 1);
		*nodeRR = DELFROMNODE(*nodeRR, vidx);
		nodeidx = minNode(RR, nodeidx, maxRNode);
		nodeRR = (RR + nodeidx);
		vidx = NODELEAST(*nodeRR);
	}

	return size;
}

/*!
 * \fn void maxStab(NODETYPE * R, NODETYPE * W, int u, int * minRNode, int * maxRNode, int * minWNode, int * maxWNode)
 * \brief Greedy heuristic for maximum stable set containing a specified vertex.
 *
 * The vertices in the specified bitmap are greedily searched for a maximum stable set. The vertices in the stable set found are removed from
 * the input bitmap and stored in the output bitmap.
 *
 * The smallest and greatest indices of non-zero nodes of the specified bitmaps are updated.
 *
 * If \c R[\c *minRNode\c ] \c == \c 0, then an error may occur.
 *
 * \param R Input bitmap of vertices to color.
 * \param W Output bitmap to store vertices as soon as they are colored.
 * \param u The vertex to expand to a stable set.
 * \param minRNode Smallest index of a non-zero node of the input bitmap.
 * \param maxRNode Greates index of a non-zero node of the input bitmap.
 * \param minWNode Smallest index of a non-zero node of the output bitmap.
 * \param maxWNode Greates index of a non-zero node of the output bitmap.
 */
void maxStab(NODETYPE * R, NODETYPE * W, int u, int * minRNode, int * maxRNode,
		int * minWNode, int * maxWNode) {
	int nodeidx = *minRNode;
	copyAll(RR, R, nodeidx, *maxRNode + 1);

	removeAll(RR, NEIG(heurg, u), nodeidx, *maxRNode + 1);
	nodeidx = minNode(RR, nodeidx, *maxRNode);

	int vidx = 0;
	int lastnodeidx = 0;
	NODETYPE * nodeR;
	NODETYPE * nodeRR;
	NODETYPE * nodeW;

	nodeRR = (RR + nodeidx);
	if (!*nodeRR)
		return;

	vidx = NODELEAST(*nodeRR);
	while (vidx >= 0) {
		removeAll(RR, NEIG(heurg, NELEM(nodeidx)+vidx), nodeidx, *maxRNode + 1);
		*nodeRR = DELFROMNODE(*nodeRR, vidx);
		nodeR = (R + nodeidx);
		*nodeR = DELFROMNODE(*nodeR, vidx);
		nodeW = (W + nodeidx);
		*nodeW = ADDTONODE(*nodeW, vidx);
		lastnodeidx = nodeidx;
		nodeidx = minNode(RR, nodeidx, *maxRNode);
		nodeRR = (RR + nodeidx);
		vidx = NODELEAST(*nodeRR);
	}
	if (lastnodeidx > *maxWNode)
		*maxWNode = lastnodeidx;
	*minRNode = minNode(R, *minRNode, *maxRNode);
	*maxRNode = maxNode(R, *maxRNode, *minRNode);
}

/*!
 * \fn int expClique(NODETYPE * R, int * C, int minRNode, int maxRNode, int topC)
 * \brief Greedy heuristic for expanding a specified clique.
 *
 * The vertices in the specified bitmap are greedily searched to entering the specified clique.
 *
 * \param R Input bitmap of vertices to color.
 * \param C The input clique.
 * \param minRNode Smallest index of a non-zero node of the input bitmap.
 * \param maxRNode Greates index of a non-zero node of the input bitmap.
 * \param topC Size of input clique.
 *
 * \return The size of the expanded clique.
 */
double expClique(NODETYPE * R, const double * w, int * C, int minRNode,
		int maxRNode, int topC) {
	int nodeidx = minRNode;
	copyAll(RR, R, nodeidx, maxRNode + 1);

	double size = 0.0;

	int t = topC;
	while (--t >= 0 && nodeidx <= maxRNode) {
		retainAll(RR, NEIG(heurg, C[t]), nodeidx, maxRNode + 1);
		nodeidx = minNode(RR, nodeidx, maxRNode);
		size += w[C[t]];
	}

	if (t >= 0) {
		while (t >= 0)
			size += w[C[t--]];
		return size;
	}

	NODETYPE * nodeRR = (RR + nodeidx);
	int vidx = NODELEAST(*nodeRR);
	while (vidx >= 0) {
		int v = NELEM(nodeidx) + vidx;
		size += w[v];
		retainAll(RR, NEIG(heurg, v), nodeidx, maxRNode + 1);
		*nodeRR = DELFROMNODE(*nodeRR, vidx);
		nodeidx = minNode(RR, nodeidx, maxRNode);
		nodeRR = (RR + nodeidx);
		vidx = NODELEAST(*nodeRR);
	}

	return size;
}

/*!
 * \fn int wich(NODETYPE * R, NODETYPE * W, const double * w, double lim, int * minRNode, int * maxRNode, int * minWNode, int * maxWNode)
 * \brief Greedy heuristic for weighted vertex coloring
 *
 * The vertices in the specified bitmap are colored, removed from this bitmap, and stored in another specified bitmap.
 * A maximum number of colors is specified. Vertices that cannot be colored with this number of colors remains in the input bitmap.
 * The colors created are represented in \c cover and \c idx arrays.
 *
 * The smallest and greatest indices of non-zero nodes of the specified bitmaps are updated.
 *
 * If \c R[\c *minRNode\c ] \c == \c 0, then an error may occur.
 *
 * \param R Input bitmap of vertices to color.
 * \param W Output bitmap to store vertices as soon as they are colored.
 * \param w Weight array.
 * \param lim Maximum coloring weight admitted.
 * \param minRNode Smallest index of a non-zero node of the input bitmap.
 * \param maxRNode Greatest index of a non-zero node of the input bitmap.
 * \param minWNode Smallest index of a non-zero node of the output bitmap.
 * \param maxWNode Greatest index of a non-zero node of the output bitmap.
 *
 * \return Weight of the coloring found.
 */
static double wich(NODETYPE * R, NODETYPE * W, double * w, double lim,
		int * minRNode, int * maxRNode, int * minWNode, int * maxWNode) {
	int size = 0;
	double weight = 0.0;
	int vidx = 0;
	int nodeidx;
	int lastnodeidx = 0;
	NODETYPE * nodeR;
	NODETYPE * nodeRR;
	NODETYPE * nodeW;

	if (cover == NULL) {
		cover = (int *) calloc((heurg->n + 1) << 1, sizeof(int));
		idx = cover + heurg->n + 1;
		memsz += (((heurg->n + 1) * sizeof(int)) << 1);
	}

	int curCover = 0;
	idx[0] = 0;
	int minRRNode, minRRidx;

	int v;
	// find vertex to a new color: weight of this vertex is the weight of a new color. It must be bounded by lim
	nodeidx = *minRNode;
	copyAll(RR, R, nodeidx, *maxRNode + 1);
	nodeRR = (RR + nodeidx);
	do {
		while (nodeidx <= *maxRNode && (vidx = NODELEAST(*nodeRR)) < 0) {
			nodeidx = minNode(RR, nodeidx + 1, *maxRNode + 1);
			nodeRR = (RR + nodeidx);
		}
		if (vidx >= 0) {
			v = NELEM(nodeidx) + vidx;
			if (weight + w[v] > lim) {
				v = -1;
				*nodeRR = DELFROMNODE(*nodeRR, vidx);
			} else {
				minRRNode = nodeidx;
				minRRidx = vidx;
			}
		} else
			v = -1;
	} while (vidx >= 0 && v < 0);

	while (v >= 0) {
		// create new color with weight of v
		weight += w[v];
		if (nodeidx < *minWNode)
			*minWNode = nodeidx;
		while (vidx >= 0) {
			int v = NELEM(nodeidx) + vidx;
			removeAll(RR, NEIG(heurg, v), nodeidx, *maxRNode + 1);
			*nodeRR = DELFROMNODE(*nodeRR, vidx);
			nodeR = (R + nodeidx);
			*nodeR = DELFROMNODE(*nodeR, vidx);
			nodeW = (W + nodeidx);
			*nodeW = ADDTONODE(*nodeW, vidx);

			cover[curCover++] = v;

			lastnodeidx = nodeidx;
			nodeidx = minNode(RR, nodeidx, *maxRNode);
			nodeRR = (RR + nodeidx);
			vidx = NODELEAST(*nodeRR);
		}
		if (lastnodeidx > *maxWNode)
			*maxWNode = lastnodeidx;
		*minRNode = minNode(R, *minRNode, *maxRNode);
		*maxRNode = maxNode(R, *maxRNode, *minRNode);

		idx[++size] = curCover;

		// find vertex to a new color: weight of this vertex is the weight of a new color. It must be bounded by lim
		nodeidx = minRRNode;
		copyAll(RR, R, nodeidx, *maxRNode + 1);
		nodeRR = (RR + nodeidx);
		*nodeRR &= (-1LL << (minRRidx + 1));
		do {
			while (nodeidx <= *maxRNode && (vidx = NODELEAST(*nodeRR)) < 0) {
				nodeidx = minNode(RR, nodeidx + 1, *maxRNode + 1);
				nodeRR = (RR + nodeidx);
			}
			if (vidx >= 0) {
				v = NELEM(nodeidx) + vidx;
				if (weight + w[v] > lim) {
					v = -1;
					*nodeRR = DELFROMNODE(*nodeRR, vidx);
				} else {
					minRRNode = nodeidx;
					minRRidx = vidx;
				}
			} else
				v = -1;
		} while (vidx >= 0 && v < 0);
	}

	idx[++size] = -1;
	return weight;
}

/*!
 * \fn int fracColoring(NODETYPE * R, NODETYPE * W, int lim, int * minRNode, int * maxRNode, int * minWNode, int * maxWNode)
 * \brief Greedy heuristic for fractional coloring.
 *
 * The vertices in the specified bitmap are colored, removed from this bitmap, and stored in another specified bitmap.
 * A maximum number of colors is specified. Vertices that cannot be colored with this number of colors remains in the input bitmap.
 *
 * The smallest and greatest indices of non-zero nodes of the specified bitmaps are updated.
 *
 * If \c R[\c *minRNode\c ] \c == \c 0, then an error may occur.
 *
 * \param R Input bitmap of vertices to color.
 * \param W Output bitmap to store vertices as soon as they are colored.
 * \param lim Maximum number of colors that can be used.
 * \param minRNode Smallest index of a non-zero node of the input bitmap.
 * \param maxRNode Greates index of a non-zero node of the input bitmap.
 * \param minWNode Smallest index of a non-zero node of the output bitmap.
 * \param maxWNode Greates index of a non-zero node of the output bitmap.
 *
 * \return The number of colors used.
 */
double fracColoring(NODETYPE * R, NODETYPE * W, const double * w, double lim,
		int * minRNode, int * maxRNode, int * minWNode, int * maxWNode) {
	if (lim < heurg->maxcq - 2)
		return greedyColoring(R, W, w, lim, minRNode, maxRNode, minWNode,
				maxWNode);

	int size = wich(R, W, w, lim, minRNode, maxRNode, minWNode, maxWNode);

	if (lim >= 3 && size == lim) {
		int vidx;
		NODETYPE * nodeS;
		NODETYPE * nodeE;
		NODETYPE * nodeEE;

		if (E == NULL) {
			int nnodes = NODEIDX(heurg->n-1) + 1;
			E = (NODETYPE *) calloc((nnodes << 1) + nnodes, WSIZE);
			EE = E + nnodes;
			S = EE + nnodes;
			memsz += (nnodes << (LOGW + 1)) + nnodes;
		} else {
			DELALL(EE + *minWNode, *maxWNode - *minWNode + 1);
			DELALL(S + *minWNode, *maxWNode - *minWNode + 1);
		}

		int tsz = 0, nsz = size;
		int k;

		int i, curColor;
		int minSNode;
		int maxSNode;
		int minENode, maxENode;

		for (k = 1; k == 1 || (nsz + tsz) / k < tsz / (k - 1); k++) {
			minSNode = *minWNode;
			maxSNode = *maxWNode;
			tsz += nsz;
			COPYALL(E+minSNode, EE+minSNode, maxSNode - minSNode + 1);
			for (curColor = 0; curColor < nsz - 1; curColor++) {
				for (i = idx[curColor]; i < idx[curColor + 1]; i++)
					S[NODEIDX(cover[i])] =
							ADDTONODE(S[NODEIDX(cover[i])], IDXINNODE(cover[i]));

				addAll(E, S, minSNode, maxSNode + 1);
				DELALL(EE + minSNode, maxSNode - minSNode + 1);
				for (; i < idx[curColor + 2]; i++)
					removeAll(E, NEIG(heurg, cover[i]), minSNode, maxSNode + 1);

				minENode = minNode(E, minSNode, maxSNode);
				maxENode = maxNode(E, maxSNode, minENode);
				nodeE = (E + minENode);
				vidx = NODELEAST(*nodeE);
				while (vidx >= 0) {
					int v = NELEM(minENode) + vidx;
					removeAll(E, NEIG(heurg, v), minENode, maxENode + 1);
					*nodeE = DELFROMNODE(*nodeE, vidx);
					nodeS = (S + minENode);
					*nodeS = DELFROMNODE(*nodeS, vidx);
					nodeEE = (EE + minENode);
					*nodeEE = ADDTONODE(*nodeEE, vidx);
					minENode = minNode(E, minENode, maxENode);
					nodeE = (E + minENode);
					vidx = NODELEAST(*nodeE);
				}
			}

			for (i = idx[curColor]; i < idx[curColor + 1]; i++)
				S[NODEIDX(cover[i])] =
						ADDTONODE(S[NODEIDX(cover[i])], IDXINNODE(cover[i]));
			minSNode = minNode(S, minSNode, maxSNode);
			maxSNode = maxNode(S, maxSNode, minSNode);
			nsz = wich(S, E, w, lim, &minSNode, &maxSNode, &minENode,
					&maxENode);
		}
		if (k > 2)
			greedyColoring(R, W, w, size - (tsz / (k - 1)), minRNode, maxRNode,
					minWNode, maxWNode);
	}

	return size;
}
